// //整数数组 nums 按升序排列，数组中的值 互不相同 。

// 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。

// 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。

// 来源：力扣（LeetCode）
// 链接：https://leetcode-cn.com/problems/search-in-rotated-sorted-array
// 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public:
	int search(vector<int>& nums, int target) {
		int rot = searchrot(nums, 0, nums.size() - 1, (nums.size() - 1) / 2);
		if (target <= nums[nums.size() - 1]){
			return searchtarget(nums, rot, nums.size() - 1, (nums.size() - 1) / 2, target);
		}
		else{
			return searchtarget(nums, 0, rot - 1, (nums.size() - 1) / 2, target);
		}

	}
	int searchrot(vector<int>& nums, int  first, int last, int mid) {//找旋转点
		if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
			return mid;
		if (nums[mid] < nums[first]){
			last = mid;
			searchrot(nums, first, last, (last + first) / 2);
		}
		else{
			first = mid;
			searchrot(nums, first, last, (last + first) / 2);
		}
	}
	int searchtarget(vector<int>& nums, int  first, int last, int mid,int target)//二分递归排序
	{
		//vector<int> nums2{ 0,2,5,6,7,8,9 };
		if (nums[mid] == target){
			return mid;
		}
		if (first >= last){
			return 99;
		}
		if (nums[mid] > target){
			last = mid-1;
			searchtarget(nums, first, last, (last + first) / 2,target);
		}
		else {
			first = mid+1;
			searchtarget(nums, first, last, (last + first) / 2, target);
		}
	}
};//我的算法相当复杂
// class Solution {
// public:
// int search(const vector<int>& nums, int target) {
// int first = 0, last = nums.size();
// while (first != last) {
// const int mid = first + (last - first) / 2;
// if (nums[mid] == target)
// return mid;
// if (nums[first] <= nums[mid]) {
// if (nums[first] <= target && target < nums[mid])
// last = mid;
// else
// first = mid + 1;
// } else {
// if (nums[mid] < target && target <= nums[last-1])
// first = mid + 1;
// else
// last = mid;
// } }
// return -1;
// }
// };大佬算法